package weekMatch.two_105;

import javafx.concurrent.Worker;
import javafx.scene.chart.Axis;

import java.util.*;

public class LeeCode_02 {
    public static void main(String[] args) {
//        System.out.println(minExtraChar("leetscode", new String[]{"leet", "code", "leetcode"}));
        System.out.println(minExtraChar("dwmodizxvvbosxxw",
                new String[]{"ox","lb","diz","gu","v","ksv","o","nuq","r","txhe","e","wmo",
                        "cehy","tskz","ds","kzbu"}));
    }
    private static int minExtraChar(String s, String[] dictionary) {
        Map<Character, List<String>> map = new HashMap<>();
        for (String son : dictionary) {
            char last = son.charAt(son.length() - 1);
            if (map.containsKey(last)){
                map.get(last).add(son);
            }else {
                List<String> list = new ArrayList<>();
                list.add(son);
                map.put(last, list);
            }
        }
        int n = s.length();
        int[] dp = new int[n];
        int i = 1, max = 0;
        for (String son : dictionary) {
            if (son.length() == 1 && (s.charAt(0) + "").equals(son)) {
                dp[0] = 1;
                max = 1;
                break;
            }
        }
        while (i < n){
            char last = s.charAt(i);
            dp[i] = max;
            if (map.containsKey(last)){
                for (String word : map.get(last)) {
                    int len = word.length();
                    if (i - len + 1 >= 0 && s.substring(i - len + 1, i + 1).equals(word)){
                        dp[i] = Math.max((i - len < 0 ? 0 : dp[i - len]) + word.length(), dp[i]);
                    }
                }
            }
            max = Math.max(max, dp[i]);
            i++;
        }
        return n - dp[n - 1];
    }
}
